//字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 
//
// 
//
// 示例： 
//
// 
//输入：S = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca", "defegde", "hijhklij"。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
// 
//
// 
//
// 提示： 
//
// 
// S的长度在[1, 500]之间。 
// S只包含小写字母 'a' 到 'z' 。 
// 
// Related Topics 贪心 哈希表 双指针 字符串 👍 714 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class PartitionLabels {
    public static void main(String[] args) {
        Solution solution = new PartitionLabels().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> partitionLabels(String s) {
            List<Integer> list = new LinkedList<>();
            char[] chars = s.toCharArray();
            int[] edge = new int[26]; // 表示每个字母对应的最大出现的位置
            int idx = 0;    // 表示当前索引
            int last = -1;  // 默认为-1，相减就不用+1，就直接能求出长度（只是第一步）,后边的几步相减就是尾减尾

            // 找到每个数组的最大出现位置
            for (int i = 0; i < chars.length; i++) {
                edge[chars[i] - 'a'] = i;
            }

            for (int i = 0; i < chars.length; i++) {
                idx = Math.max(idx, edge[chars[i] - 'a']);  // 获取当前最大的边界
                if (i == idx) {  // 如果等于当前最大边界
                    list.add(i - last); // 将边界加入结果集
                    last = i;
                }
            }
            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
